#pragma once

#include<vector>
#include<string>
#include<iostream>
using namespace std;
#define red 1
#define black 0

template<class T>
struct treenode {
	treenode<T>* _left;
	treenode<T>* _right;
	treenode<T>* _parent;

	T _data;
	int color;

	treenode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
	{}
};

template<class T, class ref, class ptr>//ref是引用，ptr是指针
struct treeiterator {
	typedef treeiterator<T, ref, ptr> iterator;
	typedef treenode<T> node;
	treeiterator(node* nd)
		:_nd(nd)
	{}

	ref operator*()
	{
		return _nd->_data;
	}
	ptr operator->()
	{
		return &(_nd->_data);
	}
	iterator operator++()
	{
		node* cur = _nd;
		if (_nd->_right)
		{
			_nd = _nd->_right;
			while (_nd->_left)
			{
				_nd = _nd->_left;
			}
			return iterator(cur);
		}
		else
		{
			while (_nd->_parent)
			{
				if (_nd->_parent->_left == _nd)
				{
					_nd = _nd->_parent;
					return iterator(cur);
				}
				else
				{
					_nd = _nd->_parent;
				}
			}
			_nd = nullptr;
			return iterator(cur);
		}
	}

	iterator operator--()
	{
		node* cur = _nd;
		if (_nd->_left)
		{
			_nd = _nd->_left;
			while (_nd->_right)
			{
				_nd = _nd->_right;
			}
			return iterator(cur);
		}
		else
		{
			while (_nd->_parent)
			{
				if (_nd->_parent->_right == _nd)
				{
					_nd = _nd->_parent;
					return iterator(cur);
				}
				else
				{
					_nd = _nd->_parent;
				}
			}
			_nd = nullptr;
			return iterator(cur);
		}
	}

	bool operator!=(const iterator& s)
	{
		return _nd != s._nd;
	}

	node* _nd;
};

template<class K, class V, class kofval>
class rbtree {
public:

	typedef treenode<V> node;
	typedef treeiterator<V, V&, V*> iterator;
	typedef treeiterator<V, const V&, const V*> const_iterator;

	iterator begin()
	{
		node* cur = root;
		while (cur->_left)
		{
			cur = cur->_left;
		}
		return iterator(cur);
	}

	iterator end()
	{
		return iterator(nullptr);
	}

	const_iterator cbegin()const
	{
		node* cur = root;
		while (cur->_left)
		{
			cur = cur->_left;
		}
		return const_iterator(cur);
	}

	const_iterator cend()
	{
		return const_iterator(nullptr);
	}

	pair<iterator, bool>  insert(const V& val)
	{
		if (root == nullptr)
		{
			root = new node(val);
			root->color = black;
			return make_pair(iterator(root), true);
		}
		kofval getk;
		K key = getk(val);
		node* parent = nullptr;
		node* cur = root;
		while (cur)
		{
			if (key > getk(cur->_data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (key < getk(cur->_data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return make_pair(iterator(cur), false);
			}
		}
		cur = new node(val);
		cur->color = red;
		cur->_parent = parent;
		if (key > getk(parent->_data))//右边
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}//添加了节点

		node* child = cur;
		node* uncle = nullptr;
		node* grandfather = parent->_parent;
		while (child)//先判断父亲颜色，如果先找叔叔，有可能grandfather是nullptr，此时调用他的right，left违规操作
		{
			if (parent->color == black)
				return make_pair(iterator(cur), true);//否则说明两个红了，child parent
if (grandfather->_left == parent)
{
	uncle = grandfather->_right;
}
else
{
	uncle = grandfather->_left;
}//找到叔叔节点

if (uncle && uncle->color == red)  //叔叔存在且叔叔是红的，就把祖父变成红的，uncle parent变成黑的，再去迭代
{
	uncle->color = black;
	parent->color = black;
	grandfather->color = red;

	child = grandfather;//再去递归,改新的值
	parent = child->_parent;
	if (parent == nullptr)//说明到根了，根成红的了
	{
		root->color = black;
		return make_pair(iterator(cur), true);
	}
	//只有这种情况会发生迭代，并且这种情况是child的parent也是red，因此如果有parent，就一定有grandfather
	//如果parent是nullptr,就说明child就是root本身，那只需将root变成黑色
	grandfather = parent->_parent;//写在上面，有可能parent==nullptr,此时再去找grandparent内存报错,因此先判断
}

else//叔叔没有或者色不对(黑色)，四种情况，每一种弄完都break
{
	if (grandfather->_left == parent && parent->_left == child)
	{
		rightmove(grandfather, parent);
		parent->color = black;
		grandfather->color = red;
		if (grandfather == root)
		{
			root = parent;
		}
	}

	else if (grandfather->_right == parent && parent->_right == child)
	{
		leftmove(grandfather, parent);
		parent->color = black;
		grandfather->color = red;
		if (grandfather == root)
		{
			root = parent;
		}
	}

	else if (grandfather->_left == parent && parent->_right == child)
	{
		leftmove(parent, child);
		rightmove(grandfather, child);
		child->color = black;
		grandfather->color = red;
		if (grandfather == root)
		{
			root = child;
		}
	}

	else if (grandfather->_right == parent && parent->_left == child)
	{
		rightmove(parent, child);
		leftmove(grandfather, child);
		child->color = black;
		grandfather->color = red;
		if (grandfather == root)
		{
			root = child;
		}
	}
	return make_pair(iterator(cur), true);
}
		}
	}
	void leftmove(node* parent, node* child)
	{
		kofval getk;
		node* grandfather = parent->_parent;
		node* childleft = child->_left;
		parent->_right = child->_left;
		child->_left = parent;
		parent->_parent = child;
		child->_parent = grandfather;
		if (grandfather)
		{
			if (getk(parent->_data) > getk(grandfather->_data))//右枝
			{
				grandfather->_right = child;
			}
			else
			{
				grandfather->_left = child;
			}
		}
		else//grandfather是nullptr,说明parent就是root
		{
			root = child;
		}
		if (childleft)
		{
			childleft->_parent = parent;
		}
	}

	void rightmove(node* parent, node* child)
	{
		kofval getk;
		node* grandfather = parent->_parent;
		node* childright = child->_right;

		parent->_left = child->_right;
		child->_right = parent;
		parent->_parent = child;
		child->_parent = grandfather;
		if (grandfather)
		{
			if (getk(child->_data) < getk(grandfather->_data))
				grandfather->_left = child;
			else
				grandfather->_right = child;
		}
		else
		{
			root = child;
		}
		if (childright)
			childright->_parent = parent;
	}

private:
	node* root = nullptr;
};